১. Longest Common Subsequence (LCS)
বর্ণনা: Longest Common Subsequence (LCS) হলো দুটি সিকোয়েন্সের মধ্যে সবচেয়ে দীর্ঘ একটি সাবসিকোয়েন্স খুঁজে বের করার সমস্যা, যেখানে সাবসিকোয়েন্সের উপাদানগুলি উভয় সিকোয়েন্সের মধ্যে কেবল তাদের উপস্থিতি সঠিক অর্ডারে থাকতে হবে, কিন্তু ধারাবাহিকভাবে নয়।
উদাহরণ
- সিকোয়েন্স 1: "ABCBDAB"
- সিকোয়েন্স 2: "BDCAB"
- LCS: "BCAB" (দৈর্ঘ্য 4)
ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করে LCS এর সমাধান
def lcs(X, Y):
m = len(X)
n = len(Y)
# একটি 2D তালিকা তৈরি করা
L = [[0] * (n + 1) for _ in range(m + 1)]
# LCS গণনা করা
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
L[i][j] = L[i - 1][j - 1] + 1
else:
L[i][j] = max(L[i - 1][j], L[i][j - 1])
return L[m][n] # LCS এর দৈর্ঘ্য ফেরত দেওয়া
# উদাহরণ ডেটা
X = "ABCBDAB"
Y = "BDCAB"
print("Length of Longest Common Subsequence:", lcs(X, Y)) # Output: 4
২. 0/1 Knapsack Problem
বর্ণনা: 0/1 Knapsack Problem হলো একটি অপ্টিমাইজেশন সমস্যা যেখানে একটি সীমিত ওজন ধারণক্ষমতা (capacity) সহ একটি ব্যাগে (knapsack) কিছু আইটেমের মধ্যে সর্বাধিক মূল্য (value) সংরক্ষণের জন্য আইটেমগুলি নির্বাচন করতে হবে। প্রতিটি আইটেমের একটি নির্দিষ্ট ওজন (weight) এবং মূল্য (value) থাকে, এবং একটি আইটেম একটি বারই নেওয়া যেতে পারে (0/1 অর্থাৎ, সম্পূর্ণ বা কিছুই নয়)।
উদাহরণ
- আইটেম:
- আইটেম 1: (ওজন 2, মূল্য 3)
- আইটেম 2: (ওজন 3, মূল্য 4)
- আইটেম 3: (ওজন 4, মূল্য 5)
- ব্যাগের ধারণক্ষমতা: 5
- সর্বাধিক মূল্য: 7 (আইটেম 1 এবং আইটেম 2 নিয়ে)
ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করে Knapsack Problem সমাধান
def knapsack(weights, values, capacity):
n = len(values)
# একটি 2D তালিকা তৈরি করা
K = [[0] * (capacity + 1) for _ in range(n + 1)]
# Knapsack গণনা করা
for i in range(n + 1):
for w in range(capacity + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif weights[i - 1] <= w:
K[i][w] = max(K[i - 1][w], values[i - 1] + K[i - 1][w - weights[i - 1]])
else:
K[i][w] = K[i - 1][w]
return K[n][capacity] # সর্বাধিক মূল্য ফেরত দেওয়া
# উদাহরণ ডেটা
weights = [2, 3, 4]
values = [3, 4, 5]
capacity = 5
print("Maximum value in Knapsack:", knapsack(weights, values, capacity)) # Output: 7
উপসংহার
Longest Common Subsequence (LCS) এবং 0/1 Knapsack Problem হল ডাইনামিক প্রোগ্রামিং ভিত্তিক সমস্যাগুলির দুটির উদাহরণ। LCS সমস্যা টেক্সট বা সিকোয়েন্স বিশ্লেষণে ব্যবহৃত হয়, যখন 0/1 Knapsack Problem অপ্টিমাইজেশনের জন্য প্রযোজ্য। উভয় সমস্যার সমাধানে ডাইনামিক প্রোগ্রামিং কৌশল ব্যবহার করা হয়, যা একটি কার্যকরী এবং দক্ষ সমাধান প্রদান করে।
